# 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

#回溯算法
"""
回溯算法是一种用于解决问题的通用算法，它通过尝试所有可能的解决方案来找到问题的一个或所有解。如果当前的选择不满足条件，算法会撤销上一步选择，并尝试其他可能性。这种方法常用于解决组合优化问题、约束满足问题等。
回溯算法的主要特点：
试探法：逐步构建解决方案，每一步都尝试所有可能的选择。
撤销操作：如果当前选择不能导致最终解，则撤销上一步选择，尝试其他选择。
递归实现：通常使用递归来实现回溯过程。
常见应用场景：
八皇后问题：在8×8的棋盘上放置8个皇后，使得它们互不攻击。
数独求解：填充数独中的空格，使其满足数独规则。
迷宫问题：寻找从起点到终点的路径。


就是构建规则 然后去迭代
"""
class Solution:
    def generateParenthesis(self, n: int) -> list[str]:
        m = n * 2  # 括号长度
        ans = []
        path = [''] * m  # 所有括号长度都是一样的 m

        def dfs(i: int, open: int) -> None:
            if i == m:  # 括号构造完毕
                ans.append(''.join(path))  # 加入答案
                return
            if open < n:  # 可以填左括号
                path[i] = '('  # 直接覆盖
                dfs(i + 1, open + 1)  # 多了一个左括号
            if i - open < open:  # 可以填右括号
                path[i] = ')'  # 直接覆盖
                dfs(i + 1, open)

        dfs(0, 0)
        return ans

    def generateParenthesis2(self, n: int) -> list[str]:
        m = n * 2  # 括号长度
        res = []
        char1 = [''] * m  # 所有括号长度都是一样的 m

        def nfs(i, j):

            if i == m:
                res.append(''.join(char1))
                return
            if (j < n):
                char1[i] = '['
                nfs(i + 1, j + 1)
            if (i - j < j):
                char1[i] = ']'
                nfs(i + 1, j)

        nfs(0, 0)
        return res


sol = Solution()
print(sol.generateParenthesis2(4))
